Digital signal processing (DSP) techniques are commonly used to manipulate and translate a wide variety of input signals from one form to another. Typically, analog signals such as audio are converted to digital signal form and operated on, or "processed," using digital circuitry. Because the signals are in digital signal form, they are virtually immune from numerous signal degradation problems inherent with analog signal processing. These problems include, for example, voltage and temperature drift in the host circuitry, component tolerance and aging, and EMI-induced power supply noise.
A significant part of many DSP applications includes using DSP techniques to filter signals. Digital filters allow for very precise signal processing because digital filters provide sharp cutoff characteristics, exact linear phase responses and even arbitrary phase responses.
One type of digital filter, known as the Finite Impulse Response (FIR) filter, is used for signal correlation and signal convolution in a wide variety of applications, including for example high-frequency radio communication and RADAR signal processing.
The FIR filter is a discrete linear time-invariant system having an output that is based on the weighted summation of a finite number of past inputs.
Correlation is a technique that is widely used in electronic systems to indicate the similarity or dissimilarity between two signals (also referred to as functions or waveforms). Such a correlation is obtained by shifting one of the waveforms by an amount of time equal to .tau., and then multiplying the shifted waveform with the other waveform and integrating the product. As a result: two identical signals will have a maximum positive correlation; a signal will have a maximum negative correlation with its polar opposite (the same signal rotated 180 degrees about the X axis); and a signal will have a zero or negligible correlation with a totally dissimilar function, for example, a function correlated with a noise signal. Correlation is advantageous because it exhibits many useful signal characteristics, such as the ability to recover a signal from noise, the ability to estimate delay, the ability to characterize signals.
Convolution is a mathematical process that is closely related to the correlation process and is also used in DSP filtering. In convolution, however, one signal is time reversed (shifted about the Y axis or where time equals 0) before being shifted by .tau.. The convolution process occurs in filters where the output of a filter, f(t), is the convolution of the input function, d(t), with the impulse response of the filter, h(t). In discrete time, the convolution of two signals x(t) and y(t) is defined by Equation 1, as follows: ##EQU1##
As reflected in Equation 1, convolution (like correlation) requires N multiply-and-accumulate operations for each sample of Cxy(m), where N is the number of convolution points having a size dependent upon the duration of the two functions or their periodicity if they are periodic. The parameters "k" and "m" are used to index the sample points of the respective input signals.
The convolution procedure requires operation upon two functions. In the field of signal filtering, one function is that of the (usually fixed) filter function. The other function is the variable input data or samples. Since the invention takes place in the digital domain, both functions are expressed as a stream of whole numbers. Each number is the "value" of the represented function at a discrete point. Therefore, each function may be expressed as a stream or sequence of values in time.
For real time applications in which signals are processed as they are received, data processing must occur very quickly. More specifically, the DSP system must perform the necessary calculations fast enough to accommodate the Nyquist rate (over two times the bandwidth of the sampled signal). As stated above, each sample Cxy(m) requires N multiply-and-accumulate operations. This is because the summation must be calculated for every value of k, from (k=0) through (k=(N-1)).
In a system designed to process signals having frequencies up to 50 MHz, for example, the sampling rate (Nyquist rate) must be at least 100 MHz (100 mega-samples/second) which corresponds to a period of ten nanoseconds. This means that the system has ten nanoseconds to accomplish N multiply-and-accumulate operations. If N is equal to ten (meaning that the filter function is ten samples wide) then each of the ten multiply-and-accumulate operations must be accomplished in one nanosecond. This would be a formidable task for even modern day electronics.
In known DSP implementations, this processing-speed problem is addressed by performing all calculations in parallel. In hardware, this task is accomplished by simultaneously using N multipliers (one for each multiply operation dictated by Equation 1) and summing the N results. Applying this solution to the example above, this arrangement would provide ten nanoseconds, rather than one nanosecond, to perform each of the ten multiply-and-accumulate operations. This solution, however, is often undesirable because of cost, power or space restrictions on the host system.
As semiconductor technology has progressed, these restrictions have been partly mitigated by increasing the circuit integration density on a single chip and using more advanced semiconductor technology requiring less power. For example, a device like SGS-Thomson's IMS A100 incorporates thirty-two multiply-adders with an input data rate of 5 MHz at 8 bits. Unfortunately, circuits such as this are expensive and limited in speed. For video applications a faster device is required such as the cascadable Harris HSP43891 which has eight multiply-summers, and has a maximum input data rate of 30 MHz. Most real-world applications require tens of multipliers per input sample and thus would require several of these expensive devices. While 30 MHz is a sufficient rate for video, RADAR and LADAR operate in the 100-1000 MHz range. Off-the-shelf convolvers operating at these data rates are not yet available and will be very expensive and bulky. A monolithic custom device using conventional circuit implementations could be built but would be limited in the number of multipliers. Thus a simpler solution is needed for both the cost-conscious commercial world and for high-speed military needs.
A conventional approach to real-time digital convolution, using an sample function with non-specific input data, is exemplified by way of FIGS. 1a, 5, 6a and 6b. FIG. 1a is a graph of a filter coefficient stream ("FCS"). The non-specific input data is represented by the notation A.sub.1, where "t" shows the relative position of the input data points, as a sample in the time domain. Using Equation 1, the convolution of this sample function is illustrated in FIG. 5 for times (t.sub.-1, t.sub.0, t.sub.1, . . . t.sub.6) for each of "n" samples.
FIG. 6(a) shows the conventional high-speed circuit approach for implementing this convolution, using five multipliers arranged in parallel with a summation circuit 601 providing the convolution results, depicted as (Z.sub.n). In practice, the summation circuit 601 is implemented by several 2-input adders as shown in FIG. 6(c). Specifically a total of N-1 adders are required for the conventional implementation. The table shown in 6(b) illustrates the summation outputs as each of the samples is processed from the lowest-positioned of the multipliers to the highest-positioned of the multipliers, and assuming that A.sub.0 is the first data sample having a non-zero value.
Accordingly, for the conventional convolution implementation shown in FIGS. 6(a), (b) and (c), four adders and five multiply operations are required for each output value of "n". Larger and more complex functions require even more multipliers and adders, and the corresponding complexity required for these operations renders a system design which is costly in terms of both power and circuit real estate.
There is therefore a need for digital signal processing approach, useful for correlation and convolution, which overcomes the above-mentioned shortcomings.